#include <iostream>
#include <windows.h>
using namespace std;

//蛮力法求解最大子段和问题
double MaxSubsequenceSum(double a[], int n, int& low, int& high)
{
    double maxSum = 0.0;

    for (int i = 0; i < n; i++)        // 子序列起始位置
    {
        double tempSum = 0.0;
        for (int j = i; j < n; j++)    // 子序列终止位置
        {
            tempSum += a[j];
            if (tempSum > maxSum)      // 更新最大和值以及记录子序列起始和终止位置
            {
                low = i;
                high = j;
                maxSum = tempSum;
            }
        }
    }
    return maxSum;
}

//分治法求解最大子段和问题
double MaxSubsequenceSum(double a[], int left, int right)
{
    // 设置递归终止条件
    if (left == right)
    {
        return a[left];
    }

    int middle = (left + right) / 2;

    double leftMaxSum = MaxSubsequenceSum(a, left, middle);          // 求左半部分最大子序列和
    double rightMaxSum = MaxSubsequenceSum(a, middle + 1, right);    // 求右半部分最大子序列和

    // 处理左右边界问题：最大子序列跨越中间
    double maxLeftBorderSum = 0;
    double maxRightBorderSum = 0;
    double tempSum;

    tempSum = 0;
    for (int i = middle; i >= left; i--)
    {
        tempSum += a[i];
        if (tempSum > maxLeftBorderSum)
        {
            maxLeftBorderSum = tempSum;     // 左边包含边界最大序列和
        }
    }

    tempSum = 0;
    for (int i = middle + 1; i < right; i++)
    {
        tempSum += a[i];
        if (tempSum > maxRightBorderSum)
        {
            maxRightBorderSum = tempSum;    // 右边包含边界最大序列和
        }
    }

    double maxMiddleSum = maxRightBorderSum + maxLeftBorderSum;        // 跨越中间最大子序列和等于两部分边界之和

    return max(leftMaxSum, maxMiddleSum, rightMaxSum);         // 返回三个部分的最大子序列和
}

//动态规划法求解最大子段和问题
double MaxSubsequenceSum(double a[], int n)
{
    double tempSum = 0.0,
        maxSum = 0.0;
    for (int i = 0; i < n; i++)   // 子问题后边界
    {
        tempSum = (tempSum + a[i]) > a[i] ? (tempSum + a[i]) : a[i];
        if (tempSum > maxSum)   // 更新最大和
        {
            maxSum = tempSum;
        }
    }
    return maxSum;
}

int main()
{
    double a[] = { 4, -3, 5, -2, -1, 2, 6, -2 };
    int low, high;
    double maxSum;

    LARGE_INTEGER start;
    LARGE_INTEGER end;
    LARGE_INTEGER frequency;

    QueryPerformanceFrequency(&frequency);

    QueryPerformanceCounter(&start);
    maxSum = MaxSubsequenceSum(a, 8, low, high);
    QueryPerformanceCounter(&end);
    cout << "蛮力法求解的最大子段和为：" << maxSum << endl;
    cout << "该算法运行时间为：" << double(end.QuadPart - start.QuadPart) / frequency.QuadPart * 1e6 << "微秒" << endl << endl;

    QueryPerformanceCounter(&start);
    maxSum = MaxSubsequenceSum(a, 0, 7);
    QueryPerformanceCounter(&end);
    cout << "分治法求解的最大子段和为：" << maxSum << endl;
    cout << "该算法运行时间为：" << double(end.QuadPart - start.QuadPart) / frequency.QuadPart * 1e6 << "微秒" << endl << endl;

    QueryPerformanceCounter(&start);
    maxSum = MaxSubsequenceSum(a, 8);
    QueryPerformanceCounter(&end);
    cout << "动态规划法求解的最大子段和为：" << maxSum << endl;
    cout << "该算法运行时间为：" << double(end.QuadPart - start.QuadPart) / frequency.QuadPart * 1e6 << "微秒" << endl << endl;

    cout << "子序列起始和终止位置分别为：" << low << " " << high << endl;

    system("pause");
    return 0;
}